package util;

import java.math.BigInteger;

/**
 * This class provides a selection of useful methods
 * @author Ralf
 *
 */
public class Algorithms {
	
//	private static final BigInteger[] largePrimes = {
//		new BigInteger("26893")
//		, new BigInteger("31573")
//		, new BigInteger("34871")
//		, new BigInteger("38729")
//		, new BigInteger("44641")
//		, new BigInteger("47777")
//		, new BigInteger("51853")
//		, new BigInteger("56857")
//		, new BigInteger("60601")
//		, new BigInteger("64997")
//		, new BigInteger("68483")
//		, new BigInteger("74771")
//		, new BigInteger("78569")
//		, new BigInteger("82013")
//		, new BigInteger("91571")
//		, new BigInteger("94483")
//		, new BigInteger("97829")
//		, new BigInteger("101929")
//		, new BigInteger("105251")
//		, new BigInteger("108497")
//		, new BigInteger("112253")
//		, new BigInteger("118619")
//		, new BigInteger("123707")
//		, new BigInteger("136861")
//		, new BigInteger("145253")
//		, new BigInteger("151471")
//		, new BigInteger("167117")
//		, new BigInteger("202481")
//		, new BigInteger("250091")
//		, new BigInteger("365683")
//		, new BigInteger("567451")
//		, new BigInteger("755147")
//		, new BigInteger("777109")
//		, new BigInteger("934603")
//		, new BigInteger("1054303")
//		, new BigInteger("1101143")
//		, new BigInteger("1121689")
//		, new BigInteger("1219237")
//		// the following primes are from the ietf page for ECC
//		, new BigInteger("E95E4A5F737059DC60DFC7AD95B3D8139515620F", 16)
//		, new BigInteger("C302F41D932A36CDA7A3463093D18DB78FCE476DE1A86297", 16)
//		, new BigInteger("D7C134AA264366862A18302575D1D787B09F075797DA89F57EC8C0FF", 16)
//		, new BigInteger("A9FB57DBA1EEA9BC3E660A909D838D726E3BF623D52620282013481D1F6E5377", 16)
//		, new BigInteger("D35E472036BC4FB7E13C785ED201E065F98FCFA6F6F40DEF4F92B9EC7893EC28FCD412B1F1B32E27", 16)
//		, new BigInteger("8CB91E82A3386D280F5D6F7E50E641DF152F7109ED5456B412B1DA197FB71123ACD3A729901D1A71874700133107EC53", 16)
//		, new BigInteger("AADD9DB8DBE9C48B3FD4E6AE33C9FC07CB308DB3B3C9D20ED6639CCA703308717D4D9B009BC66842AECDA12AE6A380E62881FF2F2D82C68528AA6056583A48F3", 16)
//	};

	/**
	 * Warning: Docu is out of date!
	 * Returns the integer, which comes closest to the log2 of the given BigInteger.
	 * 15 as parameter would return 4, because 2^4=16 is closer to 15 than 2^3=8.
	 * 9 as parameter would return 3. 
	 * @param x the value we want the closest integer approximation for log2
	 * @return the closest integer approximation for log2(x)
	 */
	public static BigInteger bestIntegerLog2(BigInteger x) {
		
		if (x.signum() <= 0)
			throw new IllegalArgumentException("x <= 0");

		// use the bit count to calculate the log_2(bit_count)
		int digit_count = x.bitLength();
		
		BigInteger lower;
		BigInteger higher;
		
		// the digit_count is always the upper bound
		higher = BigInteger.valueOf(digit_count);
		lower = BigInteger.valueOf(digit_count - 1);
		
		BigInteger delta_lower = exp2(lower).subtract(x).abs();
		BigInteger delta_higher = exp2(higher).subtract(x).abs();
		
		if (delta_lower.compareTo(delta_higher) <= 0) {
			// delta_lower <= delta_higher
			return lower;
		} else {
			// delta_lower > delta_higher
			return higher;
		}
//		return lower;
	}
	
	/**
	 * Returns 2 to the power of a given BigInteger number
	 * @param pow a BigInteger exponent
	 * @return 2^pow
	 */
	public static BigInteger exp2(BigInteger pow) {
		// shift bits to the left which is like doubling the value
		// check if pow is representable as int
		int tmp = pow.intValue();
		if (pow.compareTo(BigInteger.valueOf(tmp)) == 0) {
			return BigInteger.ONE.shiftLeft(tmp);
		}
		
		if (pow.testBit(0)) {
			// least significant bit is 0,
			// hence it is an even number and we can halve it without problems
			// 2*2*..*2 = 2^n = (2^(n/2))^2
			return exp2(pow.divide(new BigInteger("2"))).pow(2);
		} else {
			// pow is an odd number
			// 2*2*..*2 = 2^n = (2^(floor(n/2))^2 * 2
			return exp2(pow.divide(new BigInteger("2"))).pow(2).shiftLeft(1);
		}
	}
	
	/**
	 * Exponentiates a BigInteger by another BigInteger.
	 * It returns a given BigInteger, which represents base^exp
	 * @param base the BigInteger, which is to be exponentiated
	 * @param exp the exponent
	 * @return a BigInteger = base^exp
	 */
	public static BigInteger pow(BigInteger base, BigInteger exp) {
		// check if exp is representable as int
		int tmp = exp.intValue();
		if (exp.compareTo(BigInteger.valueOf(tmp)) == 0) {
			return base.pow(tmp);
		}
		if (exp.testBit(0)) {
			// least significant bit is 0,
			// hence it is an even number and we can halve it without problems
			// base*base*..*base = base^n = (base^(n/2))^2
			return pow(base, exp.divide(new BigInteger("2"))).pow(2);
		} else {
			// exp is an odd number
			// 2*2*..*2 = 2^n = (base^(floor(n/2))^2 * base
			return pow(base, exp.divide(new BigInteger("2"))).pow(2).multiply(base);
		}		
	}


	/**
	 * 
	 * @param dividend
	 * @param divisor
	 * @param modulus
	 * @return
	 */
	public static BigInteger remainderlessDivision(BigInteger dividend, BigInteger divisor, BigInteger modulus) {

		// we want to solve dividend / divisor mod modulus
		// dividend has to be added with multiple of modulus, if the quotient should not
		// have a remainder
		// find a k, such that (dividend + k * modulus) mod divisor = 0
		BigInteger k;

		dividend = dividend.mod(modulus);
		divisor = divisor.mod(modulus);

		// get k, such that: k * modulus (mod divisor) = 1
		k = modulus.modInverse(divisor);
		// but k * modulus (mod divisor) = opposite is needed,
		// where opposite is the distance from the dividend to the next multiple
		// of the divisor
		BigInteger remainder = dividend.mod(divisor);
		BigInteger opposite = divisor.subtract(remainder);
		k = k.multiply(opposite);
		
		BigInteger[] quotient = dividend.add(modulus.multiply(k)).divideAndRemainder(divisor);
		// assert that the remainder is zero
		assert(quotient[1].equals(BigInteger.ZERO));
		
		return quotient[0].mod(modulus);
	}
	
//	public static BigInteger getLargePrime(BigInteger minVal) {
//		for (int i = 0; i < largePrimes.length; i++) {
//			if (minVal.compareTo(largePrimes[i]) <= 0) {
//				return largePrimes[i];
//			}
//		}
//		return BigInteger.ZERO;
//	}
	
}
